Network monitoring software aims to detect problems and potential problems with networked resources. The network monitoring software is therefore concerned with how problems can propagate from one resource to the next. The network monitoring software is also concerned with, for a given resource experiencing a problem and having several component resources, isolating the source of the problem to a given component or set of components. One term for this and related goals of network monitoring software is “root cause analysis.” Root cause analysis seeks the origin of a problem, i.e., the first condition that caused a propagation of problems. The paths along which problems propagate can be represented as a dependency relationship between a first resource originating the problem and a second resource to which the problem propagates; the second resource is dependent upon the first not to cause problems. When two resources are involved this way, the dependency relationship is “binary”. More complicated dependency relationships might not be binary but may involve three or more resources. Such relationships can usually be expressed by a set of binary dependency relationships.
Directed Trees
FIG. 9A shows a directed tree 39, a data model known in the computing art. Tree 39 includes nodes 391 and edges 396. Tree 39 includes exactly one node 391 designated as its root 392. Each edge 396 has a direction 394 and connects two distinct nodes 391. A “path” is a sequence of edges 396 such that each member edge 396 shares a node 391 with its neighbor edge 396.
Direction 394 labels one of the two nodes 391 as the “departure” and the other as the “destination” for a given edge 396. A directed path goes “from” the departure node 391 of the path's first edge 396 and “to” the destination node 391 of the path's last edge 396, with neighboring edges 396 in the directed path sharing the departure node 391 of one neighbor with the destination node 391 of the other. Directed tree 39 has direction 394 determined for each edge 396 by position relative to root 392—in particular, directed trees 39 for which all edges 396 “point toward” root 392, or for which all edges 396 “point away from” root 392. A more formal definition of “pointing toward” root 392 is that every edge 396 in tree 39 begins a directed path to root 392. Likewise, “pointing away from” root 392 may be defined as every edge 396 in tree 39 ends a directed path from root 392.
Known properties of trees 39 include: “connectedness”, meaning every node 391 is connected to every other node 396 via some path in tree 39; and “path uniqueness”, meaning that a minimal path in tree 39 between a first node 391 and a second node 396 is the only such path between those nodes 396. The path is minimal in terms of its length. The “length” of a path is the number of edges it contains.
The “depth” of each node 391 is the length of the (unique) path that connects node 391 to root 392. The node 391 designated as root 392 has depth zero; all other nodes 391 have non-zero integer depth.
There is another way besides “departure” and “destination” to describe the nodes 391 of an edge 396: the node 391 with the lesser depth is called the “parent” of the other node 391, while the node 391 with greater depth is called the “child” of the parent. If A is a node 391, B is a child node 391 of A, and C is a child node 391 of B, then C is called a “grandchild” of A. Nodes 391 with no children are called “leafs”. The number of child nodes 391 of a node 391 is called the “degree” of that node 391.
Nodes 391 having the same depth are said to be on the same “level”, also known as “tier”. A tier is often specified by the number that characterizes the depth of its nodes 391. For example, “tier one” includes all nodes 391 that share edges 396 with root 392. At least two mathematical truths apply to edges 396 in tree 39 with regard to tiers (the proofs are known in the art). First, for “n” greater than zero, each tier “n” node 391 shares exactly one edge 396 with a node 391 in tier “n−1”. Second, edges 396 always join nodes 391 from different tiers—specifically, tiers that differ in depth by exactly one. A corollary of the second truth is that edges 396 never join nodes 391 within the same tier. These truths can be summarized intuitively as follows: edges 396 in tree 39 always go “up and down” between adjacent tiers, never “sideways” (within a tier) or skipping a tier; and, all nodes 391, except for root node 392, have a parent.
A first node 391 together with all its child nodes 391, grandchild nodes 391, the child nodes 391 of the grandchild nodes 391, and so forth, together with their connecting edges 396 form subtree 395. The subtree 395 just described is itself a tree 39 having the first node 391 as root 392. Because subtrees 395 have the same structure and properties as trees 39, trees 39 are said to be “self-similar”. Many recursive algorithms work well on trees 39 because trees 39 are self-similar, among other reasons.
The “distance” between two nodes 391 in tree 39 is the length of the shortest path connecting them. (Recall that because tree 39 is connected, at least one such path exists. Also, because tree 39 has path-uniqueness, there is precisely one such path.) Two nodes 391 sharing an edge 396 are connected “directly”. Another way of saying this is that their path length is one. Two nodes 391 connected by a path of length greater than one are connected “indirectly”, i.e. via intermediary nodes 391.
The direction from node 391 toward a node 391 of lesser depth is called up; toward greater depth is down. To “traverse” tree 39 means to point to its nodes 391 one after the other, where successive nodes 391 are only chosen if they are joined by edges 396.
Node 391 can data structures in addition to those necessary to participate in tree 39. Edge 396 encodes as a data structure that can contain additional data structures, in like manner. Therefore, certain attributes of the data structures for nodes 391 and edges 396 may pertain to entities not inherent to tree 39 itself—for instance, the data structures often contain attributes of the concept being modeled by tree 39.
To the degree that hierarchies have the structure of a tree, the same terms apply.